package com.java.恋上算法.数据结构._01_复杂度;

/**
 * @desc: 复杂度-斐波那契数列
 * @author: zhanghongqiang01@baijiahulian.com
 * @date: 2021/7/28/0028 上午 07:48
 */
public class Main {

    /* 0 1 2 3 4 5
     * 0 1 1 2 3 5 8 13 ....
     */

    // O(2^n)
    public static  int fib1(int n) {
        if(n<=1) {
            return n;
        }
        return fib1(n-1) + fib1(n -2);
    }

    // O(n)
   public static int fib2(int n) {
       if (n <= 1) {
           return n;
       }

       int first = 0;
       int second = 1;
       for (int i = 0; i<i-1; i++){
           int sum = first + second;
           first = second ;
           second = sum ;
       }
       return second;
   }


    public static void main(String[] args) {

    }

}
